গ্রিডি অ্যালগরিদমগুলি এমন সমস্যাগুলির সমাধানে ব্যবহৃত হয় যেখানে স্থানীয়ভাবে সর্বাধিক উপকারিতা গ্রহণ করা হয় এবং এটিকে গ্লোবাল অপ্টিমাইজেশনের দিকে নিয়ে যায়। নীচে গ্রিডি ভিত্তিক দুটি জনপ্রিয় সমস্যা, Fractional Knapsack এবং Huffman Coding আলোচনা করা হয়েছে।
১. Fractional Knapsack Problem
বর্ণনা
Fractional Knapsack Problem হল একটি অপ্টিমাইজেশন সমস্যা যেখানে আইটেমগুলি তাদের ওজনের ভিত্তিতে ভাগ করা যেতে পারে। অর্থাৎ, আপনি সম্পূর্ণ আইটেম বা এর একটি অংশ নিতে পারেন। লক্ষ্য হল knapsack এর সর্বাধিক ধারণক্ষমতার মধ্যে যতটা সম্ভব মূল্য অর্জন করা।
উদাহরণ
ধরা যাক, আপনার কাছে নিম্নলিখিত আইটেমগুলি রয়েছে:
| আইটেম | ওজন | মূল্য |
|---|---|---|
| 1 | 10 | 60 |
| 2 | 20 | 100 |
| 3 | 30 | 120 |
- ব্যাগের ধারণক্ষমতা: 50
গ্রিডি অ্যালগরিদম ব্যবহার করে সমাধান
- প্রথমে আইটেমগুলির জন্য মূল্য প্রতি ইউনিট ওজন (value/weight) গণনা করুন।
- আইটেমগুলিকে তাদের মূল্য প্রতি ইউনিট ওজনের ভিত্তিতে সাজান।
- আইটেমগুলিকে knapsack এ যুক্ত করুন যতক্ষণ না ধারণক্ষমতা পূর্ণ হয়।
উদাহরণ কোড (Python):
class Item:
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.value_per_weight = value / weight
def fractional_knapsack(capacity, items):
items.sort(key=lambda x: x.value_per_weight, reverse=True) # মূল্য প্রতি ওজনের ভিত্তিতে সাজানো
total_value = 0
for item in items:
if capacity == 0: # যদি ধারণক্ষমতা পূর্ণ হয়
break
if item.weight <= capacity:
total_value += item.value
capacity -= item.weight
else:
total_value += item.value_per_weight * capacity # অংশ নেওয়া
capacity = 0 # ধারণক্ষমতা পূর্ণ হয়ে গেছে
return total_value
# উদাহরণ ডেটা
items = [Item(10, 60), Item(20, 100), Item(30, 120)]
capacity = 50
max_value = fractional_knapsack(capacity, items)
print("Maximum value in Fractional Knapsack:", max_value) # Output: 240.0
২. Huffman Coding
বর্ণনা
Huffman Coding হল একটি ডেটা সংকোচনের অ্যালগরিদম যা অক্ষরের ফ্রিকোয়েন্সি ভিত্তিতে কোড তৈরি করে। এটি অক্ষরগুলির জন্য একটি হাফম্যান ট্রি তৈরি করে, যেখানে কম ফ্রিকোয়েন্সির অক্ষরগুলি দীর্ঘ কোড পায় এবং উচ্চ ফ্রিকোয়েন্সির অক্ষরগুলি সংক্ষিপ্ত কোড পায়।
উদাহরণ
ধরি, আমাদের অক্ষর এবং তাদের ফ্রিকোয়েন্সি:
| অক্ষর | ফ্রিকোয়েন্সি |
|---|---|
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |
গ্রিডি অ্যালগরিদম ব্যবহার করে সমাধান
- প্রতিটি অক্ষরের জন্য একটি নোড তৈরি করুন এবং সেগুলি একটি মিন হিপে যুক্ত করুন।
- দুটি সর্বনিম্ন ফ্রিকোয়েন্সির নোডকে বের করুন এবং একটি নতুন নোড তৈরি করুন, যা তাদের ফ্রিকোয়েন্সির যোগফল।
- নতুন নোডকে হিপে পুনরায় যুক্ত করুন এবং এটি পুনরাবৃত্তি করুন যতক্ষণ না একটি মাত্র নোড থাকে, যা হাফম্যান ট্রি।
উদাহরণ কোড (Python):
import heapq
from collections import defaultdict
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def huffman_coding(frequencies):
heap = []
# নোড তৈরি করা
for char, freq in frequencies.items():
heapq.heappush(heap, Node(char, freq))
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = Node(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
return heap[0] # হাফম্যান ট্রি
# উদাহরণ ডেটা
frequencies = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}
huffman_tree = huffman_coding(frequencies)
উপসংহার
গ্রিডি ভিত্তিক অ্যালগরিদমগুলি বিভিন্ন সমস্যা সমাধানে কার্যকরী এবং দক্ষ। Fractional Knapsack সমস্যা ডেটার সর্বাধিক মূল্য অর্জনের জন্য অ্যালগরিদমের কার্যকারিতা প্রদর্শন করে, যখন Huffman Coding ডেটা সংকোচনের জন্য একটি শক্তিশালী প্রযুক্তি। এই অ্যালগরিদমগুলির ব্যবহারে কার্যকরী সমস্যার সমাধান করা সম্ভব, যা সফটওয়্যার উন্নয়নে গুরুত্বপূর্ণ।
